#include <iostream>
#include <bitset>
#include <cstring>
#include "huffman.hpp"

struct				Symbol
{
	unsigned int	nbits;
	unsigned int	code;
};

struct				Encode_node
{
	unsigned int	count;
	unsigned int	parent;
};

struct				Decode_node
{
	unsigned int	value;
	unsigned int	children[2];
};

void				c14n_huffman(Symbol symbols[256])
{
	unsigned int	sortingtable[256];

	sortingtable[0] = 0;
	for (unsigned int j = 1; j < 256; ++j)
	{
		unsigned int	a = j;
		unsigned int	i;

		for (i = j; i && symbols[sortingtable[i - 1]].nbits > symbols[a].nbits; --i)
			sortingtable[i] = sortingtable[i - 1];
		sortingtable[i] = a;
	}

	for (unsigned int i = 0; i < 256; ++i)
	{
		if (symbols[sortingtable[i]].nbits > 0)
		{
			unsigned int code = 0;
			for (; i < 255; ++i)
			{
				symbols[sortingtable[i]].code = code;
				std::cout << symbols[sortingtable[i]].nbits << '\t' << std::bitset<16>(code) << std::endl;
				code = (code + 1) << (symbols[sortingtable[i + 1]].nbits - symbols[sortingtable[i]].nbits);
			}
			symbols[sortingtable[i]].code = code;
		}
	}
}

unsigned char		*huffman_encode(unsigned int const size, unsigned char const *data, unsigned int &newsize)
{
	Symbol			symbols[256];
	Encode_node		nodes[512];
	unsigned int	pq[256];
	int	pqtop;
	
	// count frequency
	for (unsigned int i = 0; i < 256; ++i)
		nodes[i].count = 0;
	for (unsigned int i = 0; i < size; ++i)
		++nodes[data[i]].count;

	// build tree	
	pq[0] = 0;
	for (unsigned int j = 1; j < 256; ++j)
	{
		unsigned int	a = j;
		unsigned int	i;

		for (i = j; i && nodes[pq[i - 1]].count < nodes[a].count; --i)
			pq[i] = pq[i - 1];
		pq[i] = a;
	}

	for (pqtop = 255; pqtop >= 0 && nodes[pq[pqtop]].count == 0; --pqtop)
		nodes[pq[pqtop]].parent = 0xffff;
	for (unsigned int j = 256; pqtop > 0; ++j)
	{
		unsigned int	i;

		nodes[pq[pqtop]].parent = j;
		nodes[pq[pqtop - 1]].parent = j;
		nodes[j].count = nodes[pq[pqtop]].count + nodes[pq[pqtop - 1]].count;
		nodes[j].parent = 0xffff;
		for (i = --pqtop; i && nodes[pq[i - 1]].count <= nodes[j].count; --i)
			pq[i] = pq[i - 1];
		pq[i] = j;
	}

	// convert tree to code
	for (unsigned int j = 0; j < 256; ++j)
	{
		symbols[j].nbits = 0;
		for (unsigned int i = nodes[j].parent; i != 0xffff; i = nodes[i].parent)
			++symbols[j].nbits;
	}

	// convert standard code to canonical code
	c14n_huffman(symbols);

	unsigned int	*codeddata = new unsigned int[(size + 256) / sizeof(unsigned int) + 1];
	unsigned int	i = 256 / sizeof(unsigned int);
	unsigned int	offset = 0;
	
	//convert write tree
	for (unsigned int j = 0; j < 256; ++j)
		((unsigned char *)codeddata)[j] = symbols[j].nbits;
	//convert data to code
	for (unsigned int j = 0; j < size; ++j)
	{
		codeddata[i] |= symbols[data[j]].code >> offset;
		offset += symbols[data[j]].nbits;
		if (offset >= sizeof(unsigned int) * 8)
		{
			offset -= sizeof(unsigned int) * 8;
			codeddata[++i] |= (symbols[data[j]].code << symbols[data[j]].nbits - offset);
		}
	}
	newsize = i * sizeof(unsigned int) - (sizeof(unsigned int) - offset / 8);
	return ((unsigned char *)codeddata);
}
/*
unsigned char		*huffman_decode(unsigned int const size, unsigned char const *data, unsigned int &newsize)
{
	Symbols			symbols[256];
	//Encode_node		nodes[511];
	unsigned int	pq[256];
	
	//construct tree
	
	if (size < 257)
		return (0);
	
	for (unsigned int i = 0; i < 256)
		symbols[i].nbits = data[i];
	
	c14n_huffman(symbols);
	
	
	//convert code to data
	for (unsigned int j = 0; j < size;)
	{
		idx = nodes[idx].children[data[j] >> offset && 1];
		if (++offset >= 8)
		{
			offset = 0;
			++j;
		}
		if (nodes[idx].value != 0xffff)
			decodeddata[i++] = nodes[idx].value;
	}
	newsize = i;
}
*/
int	main()
{
	char	text[] = "salut les petits boubou, on rentre bientot,gfdjgidfojgweqwdfg7d9r87g65we4ds7zcvgbfgnhuko;p7lo,4mmnb5f7cf/*s/q";
	unsigned int	size;
	
	huffman_encode(strlen(text), (unsigned char *)text, size);
	std::cout << size << std::endl;
	return (0);
}
